﻿#pragma once

namespace lyh
{
	template<typename T>
	struct list_node
	{
		T _data; //节点数据
		list_node<T>* _prev; //前驱指针
		list_node<T>* _next; //后继指针

		//构造
		list_node(const T& data = T())
			:_data(data)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

	template<typename T, typename Ref, typename Ptr>
	struct list_iterator
	{
		typedef list_node<T> node;

		node* _cur; //迭代器成员

		//构造
		list_iterator(node* cur)
			:_cur(cur)
		{}

		//前置++
		list_iterator& operator++()
		{
			_cur = _cur->_next;
			return *this;
		}
		//后置++
		list_iterator operator++(int)
		{
			list_iterator tmp(*this);
			_cur = _cur->_next;
			return tmp;
		}

		//前置--
		list_iterator& operator--()
		{
			_cur = _cur->_prev;
			return *this;
		}
		//后置--
		list_iterator operator--(int)
		{
			list_iterator tmp(*this);
			_cur = _cur->_prev;
			return tmp;
		}

		//解引用重载
		Ref operator*()
		{
			return _cur->_data;
		}
		Ptr operator->()
		{
			return &_cur->_data;
		}

		//比较重载
		bool operator==(const list_iterator& it)
		{
			return _cur == it._cur;
		}
		bool operator!=(const list_iterator& it)
		{
			return !(*this == it);
		}
	};

	//带头循环双向链表
	template<typename T>
	class list
	{
	public:
		typedef list_node<T> node;
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;

		//链表初始化
		void ListInit()
		{
			_head = new node;
			_head->_prev = _head;
			_head->_next = _head;
			_size = 0;
		}

		//构造
		list()
		{
			ListInit();
		}

		//拷贝构造
		list(const list& lt)
		{
			ListInit();
			for (auto e : lt)
			{
				push_back(e);
			}
		}

		//赋值重载
		void swap(const list& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		//迭代器
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		//const迭代器
		const_iterator begin() const
		{
			return _head->_next;
		}
		const_iterator end() const
		{
			return _head;
		}

		//pos位置插入
		iterator insert(iterator pos, const T& val)
		{
			node* cur = pos._cur;
			node* prev = cur->_prev;
			node* newnode = new node(val);

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;

			return newnode;
		}

		//删除pos位置
		iterator erase(iterator pos)
		{
			node* cur = pos._cur;
			node* prev = cur->_prev;
			node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;
			--_size;

			return next;
		}

		//尾插
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		//头插
		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		//头删
		void pop_front()
		{
			erase(begin());
		}
		//尾删
		void pop_back()
		{
			erase(--end());
		}

		//清除节点(除头结点)
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		size_t size()
		{
			return _size;
		}

	private:
		node* _head; //链表头结点
		size_t _size; //数据个数
	};

	void test()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.push_front(4);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_front();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.clear();
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}